package utils;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树节点类
 */
public class TreeNode {

    /**
     * 节点值
     */
    public int val;

    /**
     * 节点高度
     */
    public int height;

    /**
     * 左子节点引用
     */
    public TreeNode left;

    /**
     * 右子节点引用
     */
    public TreeNode right;

    /* 构造方法 */
    public TreeNode(int x) {
        val = x;
    }

    /**
     * 序列化编码规则请参考：
     * https://www.hello-algo.com/chapter_tree/array_representation_of_tree/
     * 二叉树的数组表示：
     * [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]
     * 二叉树的链表表示：
     *             /——— 15
     *         /——— 7
     *     /——— 3
     *    |    \——— 6
     *    |        \——— 12
     * ——— 1
     *     \——— 2
     *        |    /——— 9
     *         \——— 4
     *             \——— 8
     *
     * @param arr
     * @param i
     * @return
     */

    /**
     * 将列表反序列化为二叉树：递归
     *
     * @param arr
     * @param i
     * @return
     */
    private static TreeNode listToTreeDFS(List<Integer> arr, int i) {
        if (i < 0 || i >= arr.size() || arr.get(i) == null) {
            return null;
        }
        TreeNode root = new TreeNode(arr.get(i));
        root.left = listToTreeDFS(arr, 2 * i + 1);
        root.right = listToTreeDFS(arr, 2 * i + 2);
        return root;
    }

    /**
     * 将列表反序列化为二叉树
     *
     * @param arr
     * @return
     */
    public static TreeNode listToTree(List<Integer> arr) {
        return listToTreeDFS(arr, 0);
    }

    /**
     * 将二叉树序列化为列表：递归
     *
     * @param root
     * @param i
     * @param res
     */
    private static void treeToListDFS(TreeNode root, int i, List<Integer> res) {
        if (root == null) return;
        while (i >= res.size()) {
            res.add(null);
        }
        res.set(i, root.val);
        treeToListDFS(root.left, 2 * i + 1, res);
        treeToListDFS(root.right, 2 * i + 2, res);
    }

    /**
     * 将二叉树序列化为列表
     *
     * @param root
     * @return
     */
    public static List<Integer> treeToList(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        treeToListDFS(root, 0, res);
        return res;
    }
}
